
/**
  题目:
    在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
    示例 1:

    输入: 4->2->1->3
    输出: 1->2->3->4
    示例 2:

    输入: -1->5->3->4->0
    输出: -1->0->3->4->5
    
  思路:
     归并,快排,都可以
  
  效果:
      执行用时：1228 ms, 在所有 Go 提交中击败了5.11%的用户
      内存消耗：10.1 MB, 在所有 Go 提交中击败了5.16%的用户
*/
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */ 


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
      if(!head||!head->next){
          return head;
      }  
      ListNode* slow=head,*fast=head,*pre=head;
      while(fast&&fast->next){
          pre=slow;
          slow=slow->next;
          fast=fast->next->next;
      }
      pre->next=nullptr;//因为你要分割链表，链表是nullptr结束的
      return mergeSort(sortList(head),sortList(slow));
    }
    ListNode* mergeSort(ListNode*l1,ListNode* l2){
        ListNode* dummy=new ListNode(0);
        ListNode*cur=dummy;
        while(l1&&l2){
            if(l1->val>l2->val){
                cur->next=l2;
                l2=l2->next;
            }else{
                cur->next=l1;
                l1=l1->next;
            }
            cur=cur->next;
        }
        if (l1) cur->next = l1;
        if (l2) cur->next = l2;
        return dummy->next;
    }
};